572. 另一棵树的子树

Similar Question

leading to the advanced question

Solution Tips

方案一: 递归 + Depth 剪枝

var isSubtree = function(root, subRoot) {
    // 先计算出 subRoot 的深度, 匹配的子树只可能出现在深度对应的位置
    // 在对应的位置, 递归的判断每个节点是否相等.
    const subDepth = countDepth(subRoot, 0);
    console.log('subDepth: ', subDepth);

    // 计算 root 的 depth, 先不考虑优化吧, 先实现再说
    // const rootDepth = depth(root);

    // if (rootDepth < subDepth) return false;

    // const targetDepth = rootDepth - subDepth;

    // 再次遍历 root, 消耗 targetDepth, 为 0 时执行 isEqual 逻辑
    // 返回和 subDepth 相等 depth 的子树就行, 没必要遍历那么多次
    // 改变一下 depth 的遍历顺序, 从叶节点开始计算
    ans = false;
    rootDepth(root, 0)
    return ans;

	// 考虑: 通过 cb 合并两个 depth 函数
    function rootDepth(node, depth) {
        if (node === null) return depth;
        depth += Math.max(rootDepth(node.left, depth), rootDepth(node.right, depth));
        depth += 1;

        if (depth === subDepth && isEqual(node, subRoot)) {
            ans = true;
            // 考虑终止递归
        }

        return depth;

    }

    function isEqual(n, m) {
        if (n === null && m === null) return true;
        if (n === null || m === null) return false;

        return n.val === m.val && isEqual(n.left, m.left) && isEqual(n.right, m.right);
    }

    function countDepth(node, depth) {
        if (node === null) return depth;
        depth += Math.max(countDepth(node.left, depth), countDepth(node.right, depth));
        depth += 1;

        return depth;
    }
};